package arrays;

/**
 * Example: A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2.
 * How would you find the minimum element?
 * Modified binary search:
 * <p/>
 * Case 1: 8 1 2 3 4 5 6
 * Case 2: 3 4 5 6 7 1 2
 * Case 3: 1 2 3 4 5 6 7
 */
public class FindMinimumInReversedArray {

    public static int findMinimumElement_rotatedArray(int[] array, int startIndex, int endIndex){
        if (startIndex == endIndex){
            return array[startIndex];
        }
        if (array[startIndex] > array[endIndex]){
            int pivot = startIndex + (endIndex - startIndex)/2;
            return Math.min(findMinimumElement_rotatedArray(array, startIndex, pivot),
                    findMinimumElement_rotatedArray(array, pivot+1, endIndex));
        } else{ //  leftmost is the smallest
            return array[startIndex]; // array is sorted
        }
    }

    public static void main(String[] args) {
        int[] array1 = new int[]{8,1,2,3,4,5,6};
        int[] array2 = new int[]{3,4,5,6,7,1,2};
        int[] array3 = new int[]{1,2,3,4,5,6,7};

        System.out.println("array1 min:" + findMinimumElement_rotatedArray(array1, 0, array1.length-1));
        System.out.println("array2 min:" + findMinimumElement_rotatedArray(array2, 0, array2.length-1));
        System.out.println("array3 min:" + findMinimumElement_rotatedArray(array3, 0, array3.length-1));
    }
}